using BepuUtilities;
using BepuUtilities.Collections;
using BepuUtilities.Memory;
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Threading;

namespace BepuPhysics.CollisionDetection
{
    internal enum PreflushJobType
    {
        /// <summary>
        /// 唤醒程序中的第一阶段任务。用于标识子作业的作业索引。
        /// </summary>
        AwakenerPhaseOne,
        /// <summary>
        /// 对所有辅助进程中的单个类型的约束进行排序。由确定性预刷新用于计划添加。
        /// 不访问缓冲池;内存在主线程上分配和返回。
        /// </summary>
        SortContactConstraintType,
        /// <summary>
        /// 标识每个新约束应添加到的约束批次的第一个猜测。
        /// 不访问缓冲池;内存在主线程上分配和返回。
        /// </summary>
        SpeculativeConstraintBatchSearch,

        // 确定性约束添加被分成两个分派。待添加排序、推测性批处理搜索和正文列表添加都首先发生。
        // 实际添加过程随后与新鲜度检查器一起进行。
        // 它比不确定的路径慢,但那是要咬的子弹。

        /// <summary>
        /// 在推测性计算的批处理目标的帮助下,按照由前面的排序确定的顺序将约束添加到求解器和约束图中。局部顺序的。
        /// 在创建类型批或调整类型批大小时访问主线程缓冲池。
        /// </summary>
        DeterministicConstraintAdd,
        /// <summary>
        /// 按碰撞检测阶段确定的顺序向求解器和约束图添加约束。如果冲突检测阶段由于线程化而不确定,则
        /// 这将导致向解算器添加不确定的内容。
        /// 在创建类型批或调整类型批大小时访问主线程缓冲池。
        /// </summary>
        NondeterministicConstraintAdd,
        /// <summary>
        /// 唤醒号的第二阶段任务。用于标识子作业的作业索引。
        /// </summary>
        AwakenerPhaseTwo,
        /// <summary>
        /// 检查区域中的新鲜度字节以删除过期对。
        /// </summary>
        CheckFreshness,
    }

    [StructLayout(LayoutKind.Explicit)]
    internal struct PreflushJob
    {
        [FieldOffset(0)]
        public PreflushJobType Type;
        /// <summary>
        /// CheckFreshnity或SpeculativeConstraintBatchSearch作业的开始区域。
        /// </summary>
        [FieldOffset(4)]
        public int Start;
        /// <summary>
        /// CheckFreshnity或SpeculativeConstraintBatchSearch作业的结束区域。
        /// </summary>
        [FieldOffset(8)]
        public int End;
        /// <summary>
        /// 以SpeculativeConstraintBatchSearch或SortContactConstraintType为目标的窄阶段约束类型索引。
        /// </summary>
        [FieldOffset(12)]
        public int TypeIndex;
        /// <summary>
        /// 在其中开始一系列约束的辅助进程的索引。
        /// 由SpeculativeConstraintBatchSearch使用。
        /// </summary>
        [FieldOffset(16)]
        public int WorkerIndex;
        /// <summary>
        /// 包含要读入SortContactConstraintType和非确定ConstraintAdd任务的约束的工作线程数。
        /// </summary>
        [FieldOffset(16)]
        public int WorkerCount;
        /// <summary>
        /// 作业的索引。由AwakenerPhaseOne和AwakenerPhaseTwo任务使用。
        /// </summary>
        [FieldOffset(4)]
        public int JobIndex;
    }

    public partial class NarrowPhase<TCallbacks>
    {
        public struct SortConstraintTarget
        {
            public int WorkerIndex;
            public int ByteIndexInCache;
            // 请注意,我们在执行收集工作者索引和字节索引的初始过程时缓存句柄。
            // 虽然这确实会增加内存使用量,但请注意,1024个挂起的约束只会占用16384个字节。
            // 因此,经历严重混乱的超大型模拟可能会导致排序线程从L1溢出,但实际上永远不会从L2溢出。
            // 这种高速缓存避免了从不同的工作集重复拉入高速缓存线的需要。
            // 在混乱的大型模拟中,较差的高速缓存线利用率(因为我们只查找4-8个字节)可能会导致溢出到L3。
            // 额外的好处是,初始遍期间的访问模式是可预取的,而比较时间查找是不可预取的。
            public ulong SortKey;
        }
        Buffer<QuickList<SortConstraintTarget>> sortedConstraints;

        int preflushJobIndex;
        QuickList<PreflushJob> preflushJobs;
        Action<int> preflushWorkerLoop;
        void PreflushWorkerLoop(int workerIndex)
        {
            int jobIndex;
            while ((jobIndex = Interlocked.Increment(ref preflushJobIndex)) < preflushJobs.Count)
            {
                ExecutePreflushJob(workerIndex, ref preflushJobs[jobIndex]);
            }
        }

        struct PendingConstraintComparer : IComparerRef<SortConstraintTarget>
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public unsafe int Compare(ref SortConstraintTarget a, ref SortConstraintTarget b)
            {
                return a.SortKey.CompareTo(b.SortKey);
            }
        }

        unsafe void BuildSortingTargets(ref QuickList<SortConstraintTarget> list, int typeIndex, int workerCount)
        {
            for (int i = 0; i < workerCount; ++i)
            {
                ref var workerList = ref overlapWorkers[i].PendingConstraints.pendingConstraintsByType[typeIndex];
                if (workerList.Count > 0)
                {
                    // 这是在做冗余的整数除法,但是我们缺乏类型知识,并且不需要任何额外的内存加载。
                    var entrySizeInBytes = workerList.ByteCount / workerList.Count;
                    int indexInBytes = 0;
                    for (int j = 0; j < workerList.Count; ++j)
                    {
                        ref var constraint = ref list.AllocateUnsafely();
                        constraint.WorkerIndex = i;
                        constraint.ByteIndexInCache = indexInBytes;
                        // 请注意两个详细信息：
                        // 1)我们依赖于挂起约束添加中的内存布局。如果可冲突对没有占用前8个字节,则中断。
                        // 2)我们依赖于可碰撞对引用的顺序。狭窄的阶段应该始终保证一致的顺序。
                        constraint.SortKey = *(ulong*)(workerList.Buffer.Memory + indexInBytes);
                        indexInBytes += entrySizeInBytes;
                    }
                }
            }
        }

        unsafe void ExecutePreflushJob(int workerIndex, ref PreflushJob job)
        {
            switch (job.Type)
            {
                case PreflushJobType.CheckFreshness:
                    FreshnessChecker.CheckFreshnessInRegion(workerIndex, job.Start, job.End);
                    break;
                case PreflushJobType.SortContactConstraintType:
                    {
                        // 主线程已经为存在的所有类型分配了适当容量的列表。
                        // 我们在多个线程上对这些列表进行初始化和排序。
                        ref var list = ref sortedConstraints[job.TypeIndex];
                        BuildSortingTargets(ref list, job.TypeIndex, job.WorkerCount);

                        // 由于重复是不可能的(因为这意味着窄阶段为一对生成了两个约束),所以使用非三向排序。
                        PendingConstraintComparer comparer;
                        QuickSort.Sort(ref list.Span[0], 0, list.Count - 1, ref comparer);
                    }
                    break;
                case PreflushJobType.SpeculativeConstraintBatchSearch:
                    {
                        overlapWorkers[job.WorkerIndex].PendingConstraints.SpeculativeConstraintBatchSearch(Solver, job.TypeIndex, job.Start, job.End);
                    }
                    break;
                case PreflushJobType.NondeterministicConstraintAdd:
                    {
                        for (int i = 0; i < job.WorkerCount; ++i)
                        {
                            overlapWorkers[i].PendingConstraints.FlushWithSpeculativeBatches(Simulation, ref PairCache);
                        }
                    }
                    break;
                case PreflushJobType.DeterministicConstraintAdd:
                    {
                        for (int typeIndex = 0; typeIndex < contactConstraintAccessors.Length; ++typeIndex)
                        {
                            contactConstraintAccessors[typeIndex]?.DeterministicallyAdd(typeIndex, overlapWorkers, ref sortedConstraints[typeIndex], Simulation, PairCache);
                        }
                    }
                    break;
                case PreflushJobType.AwakenerPhaseOne:
                    {
                        Simulation.Awakener.ExecutePhaseOneJob(job.JobIndex);
                    }
                    break;
                case PreflushJobType.AwakenerPhaseTwo:
                    {
                        Simulation.Awakener.ExecutePhaseTwoJob(job.JobIndex);
                    }
                    break;
            }
        }

        protected override void OnPreflush(IThreadDispatcher threadDispatcher, bool deterministic)
        {
            var threadCount = threadDispatcher == null ? 1 : threadDispatcher.ThreadCount;

            // 在我们完成约束添加之前,必须使对缓存的约束句柄->对映射足够大,以容纳所有现有的约束
            // 我们将要添加的任何内容。不能保证我们会使用它们(可能会有一些较早的句柄可用),但我们没有提前知道的好方法。
            int newConstraintCount = 0;
            int setsToAwakenCapacity = 0;
            for (int i = 0; i < threadCount; ++i)
            {
                newConstraintCount += overlapWorkers[i].PendingConstraints.CountConstraints();
                // 这往往会大大高估真实的设置要求,但这并不重要-不管怎样,最大分配都不会很麻烦。
                setsToAwakenCapacity += overlapWorkers[i].PendingSetAwakenings.Count;
            }
            var targetConstraintCapacity = Solver.HandlePool.HighestPossiblyClaimedId + 1 + newConstraintCount;
            PairCache.EnsureConstraintToPairMappingCapacity(Solver, targetConstraintCapacity);
            // 对主解算器控制柄集执行相同的操作。我们经常使用Solver.HandleToLocation;调整大小会破坏东西。
            Solver.EnsureSolverCapacities(1, targetConstraintCapacity);
            var setsToAwaken = new QuickList<int>(setsToAwakenCapacity, Pool);
            var uniqueAwakeningsSet = new IndexSet(Pool, Simulation.Bodies.Sets.Length);
            for (int i = 0; i < threadCount; ++i)
            {
                Simulation.Awakener.AccumulateUniqueIndices(ref overlapWorkers[i].PendingSetAwakenings, ref uniqueAwakeningsSet, ref setsToAwaken);
            }
            uniqueAwakeningsSet.Dispose(Pool);
            for (int i = 0; i < threadCount; ++i)
            {
                overlapWorkers[i].PendingSetAwakenings.Dispose(overlapWorkers[i].Batcher.Pool);
            }
            (int awakenerPhaseOneJobCount, int awakenerPhaseTwoJobCount) = Simulation.Awakener.PrepareJobs(ref setsToAwaken, false, threadCount);
            if (threadCount > 1)
            {
                // 考虑到所涉及的大小,对于基本上任何模拟来说,128的固定猜测应该就足够了。过度杀伤力,但不是以令人担忧的方式。
                // 临时分配1KB的内存不是什么大不了的事,无论如何我们都只会触及它的必要子集。
                // (在某些病理情况下,仍然可以调整大小,但是约束移除器通过不安全地添加来处理它们。)
                preflushJobs = new QuickList<PreflushJob>(128 + Math.Max(awakenerPhaseOneJobCount, awakenerPhaseTwoJobCount), Pool);

                // 第一阶段：
                // 1)如果是确定性的,则对每个类型的批次进行排序。
                // 2)执行任何唤醒程序阶段1作业(成对缓存唤醒、更新唤醒的批处理引用句柄、复制唤醒的正文区域)。
                // 3)对每个新约束并行推测性地搜索最佳猜测约束批次。

                // 按照第一阶段的目标,我们必须在创造就业期间履行职责：
                // 1)扫描工作器并为要添加的排序句柄分配空间(如果确定)。
                // 2)投机性工作创造遍历每个工人包含的类型。较大的连续列表细分为多个作业。
                // 然而,我们从不费心创建跨越工人或类型之间界限的工作。虽然在某些情况下这可以将各个作业的大小降低到有用的水平以下,
                // 在这些情况下,业绩赤字也无关紧要。仅在单个列表中操作的单个作业的简单性更有价值
                // 在作业过程中跳转到不同的内存区域会产生轻微的缓存未命中成本。将这些成本捆绑到新的多线程任务的开销中并不是一件可怕的事情。

                for (int i = 0; i < threadCount; ++i)
                {
                    overlapWorkers[i].PendingConstraints.AllocateForSpeculativeSearch();
                }
                for (int i = 0; i < awakenerPhaseOneJobCount; ++i)
                {
                    preflushJobs.Add(new PreflushJob { Type = PreflushJobType.AwakenerPhaseOne, JobIndex = i }, Pool);
                }
                // 请注意,我们在Batch Finder之前创建排序作业。
                // 它们往往单独比约束批处理查找器阶段高得多,我们希望能够填补执行空白。
                // TODO：如果所有的工作都按体重进行半分类,那会很好--这只会拆分觉醒的工作创建器循环。只有在侧写建议的情况下才麻烦。
                if (deterministic)
                {
                    Pool.TakeAtLeast(PairCache.CollisionConstraintTypeCount, out sortedConstraints);
                    sortedConstraints.Clear(0, PairCache.CollisionConstraintTypeCount);
                    for (int typeIndex = 0; typeIndex < PairCache.CollisionConstraintTypeCount; ++typeIndex)
                    {
                        int countInType = 0;
                        for (int workerIndex = 0; workerIndex < threadCount; ++workerIndex)
                        {
                            countInType += overlapWorkers[workerIndex].PendingConstraints.pendingConstraintsByType[typeIndex].Count;
                        }
                        if (countInType > 0)
                        {
                            // 请注意,我们在这里实际上没有添加任何约束目标-我们让实际的工作线程来做这件事。没有理由不这样做,而且它还提取了一点额外的并行性。
                            sortedConstraints[typeIndex] = new QuickList<SortConstraintTarget>(countInType, Pool);
                            preflushJobs.Add(new PreflushJob { Type = PreflushJobType.SortContactConstraintType, TypeIndex = typeIndex, WorkerCount = threadCount }, Pool);
                        }
                    }
                }
                const int maximumConstraintsPerJob = 16; // TODO：经验调优。

                for (int typeIndex = 0; typeIndex < PairCache.CollisionConstraintTypeCount; ++typeIndex)
                {
                    for (int workerIndex = 0; workerIndex < threadCount; ++workerIndex)
                    {
                        var count = overlapWorkers[workerIndex].PendingConstraints.pendingConstraintsByType[typeIndex].Count;
                        if (count > 0)
                        {
                            var jobCount = 1 + count / maximumConstraintsPerJob;
                            var jobSize = count / jobCount;
                            var remainder = count - jobCount * jobSize;
                            int previousEnd = 0;
                            for (int i = 0; i < jobCount; ++i)
                            {
                                var jobStart = previousEnd;
                                var constraintsInJob = jobSize;
                                if (i < remainder)
                                    ++constraintsInJob;
                                previousEnd += constraintsInJob;
                                preflushJobs.Add(new PreflushJob
                                {
                                    Type = PreflushJobType.SpeculativeConstraintBatchSearch,
                                    Start = jobStart,
                                    End = previousEnd,
                                    TypeIndex = typeIndex,
                                    WorkerIndex = workerIndex
                                }, Pool);
                            }
                            Debug.Assert(previousEnd == count);
                        }
                    }
                }
                // 必须对其进行缓存,以便新鲜度检查器不会在新唤醒的条目上调度作业。
                var originalPairCacheMappingCount = PairCache.Mapping.Count;
                // var start=Stopwatch.GetTimestamp();
                preflushJobIndex = -1;
                threadDispatcher.DispatchWorkers(preflushWorkerLoop);
                // for(int i=0;i<preflushJobs.Count;++i)
                // {
                // ExecutePrefushJob(0,ref preflushJobs[i]);
                // }
                // var end=Stopwatch.GetTimestamp();
                // Console.WriteLine($"预刷新第一阶段时间(Us)：{1e6*(end-start)/Stopwatch.Frequency}");

                // 第二阶段：
                // 这里我们只处理唤醒程序的第二阶段工作(如果有的话)。这些不能在第一阶段中堆叠(因为第一阶段处理唤醒程序第一阶段作业),
                // 并且它们不能(容易地)与窄相位约束相加堆叠,因为它可能触发类型批处理大小调整。
                preflushJobs.Clear(); // 请注意作业已清除。我们正在安排新的工作。
                for (int i = 0; i < awakenerPhaseTwoJobCount; ++i)
                {
                    preflushJobs.Add(new PreflushJob { Type = PreflushJobType.AwakenerPhaseTwo, JobIndex = i }, Pool);
                }

                // start=Stopwatch.GetTimestamp();
                preflushJobIndex = -1;
                threadDispatcher.DispatchWorkers(preflushWorkerLoop);
                // for(int i=0;i<preflushJobs.Count;++i)
                // {
                // ExecutePrefushJob(0,ref preflushJobs[i]);
                // }
                // end=Stopwatch.GetTimestamp();
                // Console.WriteLine($"预刷新第二阶段时间(Us)：{1e6*(end-start)/Stopwatch.Frequency}");

                // 第三阶段：
                // 1)局部顺序约束相加。这是最强大的单个任务,它在一个线程上运行。它可以是确定性的,也可以是非确定性的。
                // 2)新鲜度检查器。许多较小的工作有望填补空白,而约束增加了完成。CPU越宽,这就越不可能实现。
                preflushJobs.Clear(); // 请注意作业已清除。我们正在安排新的工作。
                if (deterministic)
                {
                    preflushJobs.Add(new PreflushJob { Type = PreflushJobType.DeterministicConstraintAdd }, Pool);
                    // var job=new PrefushJob{Type=PrefushJobType.Definistic ConstraintAdd};
                    // ExecutePrefushJob(0,ref job);
                }
                else
                {
                    preflushJobs.Add(new PreflushJob { Type = PreflushJobType.NondeterministicConstraintAdd, WorkerCount = threadCount }, Pool);
                    // var作业=新的预作业{类型=PreflushJobType.NondeterministicConstraintAdd,工作计数=线程计数};
                    // ExecutePrefushJob(0,ref job);
                }
                FreshnessChecker.CreateJobs(threadCount, ref preflushJobs, Pool, originalPairCacheMappingCount);

                // start=Stopwatch.GetTimestamp();
                preflushJobIndex = -1;
                threadDispatcher.DispatchWorkers(preflushWorkerLoop);
                // for(int i=0;i<preflushJobs.Count;++i)
                // {
                // ExecutePrefushJob(0,ref preflushJobs[i]);
                // }
                // end=Stopwatch.GetTimestamp();
                // Console.WriteLine($"预刷新阶段3时间(Us)：{1e6*(end-start)/Stopwatch.Frequency}");

                for (int i = 0; i < threadCount; ++i)
                {
                    overlapWorkers[i].PendingConstraints.DisposeSpeculativeSearch();
                }
                if (deterministic)
                {
                    for (int i = 0; i < PairCache.CollisionConstraintTypeCount; ++i)
                    {
                        ref var typeList = ref sortedConstraints[i];
                        if (typeList.Span.Allocated)
                            typeList.Dispose(Pool);
                    }
                    Pool.Return(ref sortedConstraints);
                }
                preflushJobs.Dispose(Pool);
            }
            else
            {
                // 单螺纹。简单多了！
                // 三个任务：唤醒、新鲜度检查和添加所有挂起的约束。
                // 请注意,第一阶段更改了PairCache.Mapping.Count;必须缓存计数,以便新鲜度检查器不会费心分析新唤醒的对。
                var originalMappingCount = PairCache.Mapping.Count;
                for (int i = 0; i < awakenerPhaseOneJobCount; ++i)
                    Simulation.Awakener.ExecutePhaseOneJob(i);
                // 请注意,唤醒程序的第一阶段必须在约束刷新之前发生。第一阶段在约束批处理中注册新唤醒的约束。
                // 这不是这样做的,挂起的添加可能最终与共享正文的新唤醒约束以相同的批次结束。
                for (int i = 0; i < awakenerPhaseTwoJobCount; ++i)
                    Simulation.Awakener.ExecutePhaseTwoJob(i);
                overlapWorkers[0].PendingConstraints.FlushSequentially(Simulation, PairCache);
                FreshnessChecker.CheckFreshnessInRegion(0, 0, originalMappingCount);
            }
            for (int i = 0; i < threadCount; ++i)
            {
                overlapWorkers[i].PendingConstraints.Dispose();
            }
            if (setsToAwaken.Count > 0)
            {
                Simulation.Awakener.DisposeForCompletedAwakenings(ref setsToAwaken);
            }
            setsToAwaken.Dispose(Pool);

        }
    }
}
